package com.algorithm.learning.sort;

import java.util.Arrays;
import java.util.Stack;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/19 20:40
 **/
public class 快速排序_非递归 {

    public static void main(String[] args) {
        int[] arr = {3, 4, 6, 1, 0, 2, 6, 2};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 本身快速排序的思想是一样的，所以partition方法不变
     * @param arr
     * @param L
     * @param R
     * @return
     */
    public static int[] partition(int[] arr, int left, int right) {
        // 左区域起始位置
        int less = left - 1;
        // 右区域起始位置
        int more = right;
        // index就是当前数
        int index = left;
        while (index < more) {
            if (arr[index] < arr[right]) {
                // 如果当前数小于 右边的基数，那么左区域向右移，当前值index向右移一位，并且当前值与左区域的下一个位数进行交换
                swap(arr, ++less, index++);
            } else if (arr[index] == arr[right]) {
                //  如果当前数 等于 右边的基数，那么当前值index向右移一位即可
                index++;
            } else {
                //  如果当前数 大于 右边的基数，那么当前数与右区域的下一位数进行交换，并且右区域左移
                swap(arr, index, --more);
            }
        }
        // 最后如果当前值与右区域重叠了，那么直接把当前值与基值进行交换
        swap(arr, index, right);
        // 返回当前中间等于区域的下标范围
        return new int[] {less + 1, more};
    }

    /**
     * 这个版本的快速排序是非递归版本的，但是基本思想步骤，还是一样的，
     * 我们还是需要找到等于区域，然后不断地对左右区域进行排序，最后一定是有序的
     *
     * 我们可以使用Stack栈来进行排序
     * @param arr
     */
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        Stack<Job> stack = new Stack<>();
        stack.push(new Job(0, arr.length - 1));
        // 判断条件就是 栈不为空
        while (!stack.isEmpty()) {
            Job job = stack.pop();
            int[] equalArea = partition(arr, job.L, job.R);
            // 这里一定要注意边界，可能当前的等于区域与左区域重合了，所以需要判断一下
            if (equalArea[0] > job.L) {
                stack.push(new Job(job.L, equalArea[0] - 1));
            }
            if (equalArea[1] < job.R) {
                stack.push(new Job(equalArea[0] + 1, job.R));
            }
        }
    }

    /**
     * 我们定义一个任务，这个任务只是接受左右区域的边界
     */
    public static class Job {
        private final int L;
        private final int R;

        public Job(int l, int r) {
            L = l;
            R = r;
        }
    }



    public static void swap(int[] arr, int old, int n) {
        int temp = arr[old];
        arr[old] = arr[n];
        arr[n] = temp;
    }
}
